package a_doubleWrite;

import util.TreeNode;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 构造哈夫曼树
 * 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，
 * 记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
 * WPL最小的就是赫夫曼树
 *
 * @author: luolidong
 * @create: 2021-07-20 18:56
 * @version: 1.0
 */
public class HuffmanTree {
    public TreeNode buildTree(int[] nums) {
        PriorityQueue<TreeNode> queue = new PriorityQueue<TreeNode>((o1, o2) -> o1.val-o2.val);
        for (int n : nums) queue.offer(new TreeNode(n));

        TreeNode curNode = null;
        while (!queue.isEmpty()) {

            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();

            TreeNode node = new TreeNode(node1.val+node2.val);
            node.left = node1;
            node.right = node2;
            queue.offer(node);
            if(queue.size()==1){
                curNode = node;
                break;
            }
        }
        return curNode;
    }

    public static void main(String[] args) {
        HuffmanTree huffmanTree = new HuffmanTree();
        TreeNode node = huffmanTree.buildTree(new int[]{13,23,42,1, 8, 7, 3,5});
        System.out.println(node);
    }
}
